#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

struct node
{
	char data;
	node *lchild, *rchild;
};

node *CreateBT2(char *post /*指向后序序列开头的指针*/, char *in /*指向中序序列开头的指针*/, int n)
{
	
	char r, *p;
	
	int k;
	
	if (n <= 0 || post == nullptr || in == nullptr) //代码鲁棒性，细节必须注意
		return nullptr;
	
	r = *(post + n - 1);//树根
	node *b = (node *)malloc(sizeof(node));
	b->data = r; //我们要创建的树根节点建立好了
	
	for (p = in; p < in + n; ++p)//p走到中序序列的根结点处
		if (*p == r)
			break;
	
	k = p - in; //k是左子树节点数
	
	b->lchild = CreateBT2(post, in, k); //这两个语句最关键
	b->rchild = CreateBT2(post + k, p + 1, n - k - 1);
	
	return b;
}

/****************打印各节点***********************/
int first_flag = 0;
void layerOrder(node *root)
{
	queue<node *> ans;
	ans.push(root);
	while (!ans.empty())
	{
		node *tmp = ans.front();
		ans.pop();
		if (first_flag != 0)
		{
			cout << " ";
		}
		cout << tmp->data;
		first_flag = 1;
		if (tmp->lchild != NULL)
			ans.push(tmp->lchild);
		if (tmp->rchild != NULL)
			ans.push(tmp->rchild);
	}
}

int main()
{
	char str1[40] = {0};
	char str2[40] = {0};
	printf("请输入后序序列\n");
	scanf("%s", str1);
	
	int len1 = 0,i=0;
	while(str1[i++]!='\0')len1++;
	printf("请输入中序序列\n");
	scanf("%s", str2);
	
	int len2 = 0;
	i=0;
	while(str2[i++]!='\0')len2++;
	
	if(len1!=len2)
		printf("您的输入不合法！\n");
	
	node *root = CreateBT2(str1, str2, len1);
	
	layerOrder(root);
	return 0;
}

